#include <stdio.h>
#include <stdlib.h>



typedef struct Node {
    int data;          // 数据域
    struct Node *next;     // 指向下一个节点的指针
} Node, *LinkList;

// 插入操作
void ListInsert(LinkList L, int i, int e) {
    LinkList p = L; // 让p指向头结点
    int j = 0;      // 用于记录当前节点的位置

    // (2) 当(p非空且p不是第i-1个结点) 找到插入的位置
    while (p != NULL && j < i - 1) {
        p = p->next; // p指向下一结点
        j++;
    }

    // (3) 如果(p为空或i<1)
    if (p == NULL || i < 1) {
        printf("Error: Invalid position for insertion.\n");
        return; // 输出错误信息并返回
    }

    // (4) 生成新结点s
    LinkList newNode = (LinkList) malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Error: Memory allocation failed.\n");
        return; // 内存分配失败
    }
    newNode->data = e; // 赋值给新节点

    // (5) 让原来p的后继做结点s的后继
    newNode->next = p->next; // 新节点的后继指向原来p的后继

    // (6) 结点s作为p的后继
    p->next = newNode; // 将新节点插入链表
}

// 辅助函数，用于创建链表
void CreateList(LinkList *L, int n) {
    *L = (LinkList) malloc(sizeof(Node)); // 创建头结点
    if (*L == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return;
    }
    (*L)->next = NULL; // 初始化头结点的next指向NULL

    LinkList current = *L; // current指向头结点
    for (int i = 0; i < n; i++) {
        LinkList newNode = (LinkList) malloc(sizeof(Node));
        if (newNode == NULL) {
            fprintf(stderr, "Memory allocation failed\n");
            return;
        }
        printf("Enter data for node %d: ", i + 1);
        scanf("%d", &newNode->data);
        newNode->next = NULL; // 新节点的next指向NULL
        current->next = newNode; // 链接新节点到链表
        current = newNode; // 更新current指向新节点
    }
}

// 遍历并打印链表
void PrintList(LinkList L) {
    LinkList current = L->next; // 从头结点的下一个节点开始遍历
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 主函数
int main() {
    LinkList L;
    int n;

    printf("Enter the number of nodes: ");
    scanf("%d", &n);
    CreateList(&L, n); // 创建链表

    printf("Original List: ");
    PrintList(L); // 打印原链表

    int pos, value;
    printf("Enter position to insert: ");
    scanf("%d", &pos);
    printf("Enter value to insert: ");
    scanf("%d", &value);

    ListInsert(L, pos, value); // 插入新节点
    printf("Updated List: ");
    PrintList(L); // 打印更新后的链表

    // 释放链表的内存
    LinkList current = L->next; // 从第一个节点开始
    LinkList temp;
    while (current != NULL) {
        temp = current; // 保存当前节点
        current = current->next; // 移动到下一个节点
        free(temp); // 释放当前节点
    }
    free(L); // 释放头结点

    return 0;
}
